AustralieFrV1, Main, Exploration, bibRecord, 006368

On the Right-Seed Array of a String

Identifieur interne : 006368 ( Main/Exploration ); précédent : 006367; suivant : 006369

On the Right-Seed Array of a String

Auteurs : Michalis Christou [Royaume-Uni] ; Maxime Crochemore [Royaume-Uni, France] ; Ondrej Guth [République tchèque] ; Costas S. Iliopoulos [Royaume-Uni, Australie] ; Solon P. Pissis [Royaume-Uni]

Source :

Lecture Notes in Computer Science [ 0302-9743 ] ; 2011.

RBID : ISTEX:943A61B48CE2151B556A488A6F66336B6CB793CF

English descriptors

Abstract

Abstract: We consider the problem of finding the repetitive structure of a given fixed string y. A factor u of y is a cover of y, if every letter of y falls within some occurrence of u in y. A factor v of y is a seed of y, if it is a cover of a superstring of y. There exist linear-time algorithms for solving the minimal cover problem. The minimal seed problem is of much higher algorithmic difficulty, and no linear-time algorithm is known. In this article, we solve one of its variants – computing the minimal and maximal right-seed array of a given string. A right seed of y is the shortest suffix of y that it is a cover of a superstring of y. An integer array RS is the minimal right-seed (resp. maximal right-seed) array of y, if RS[i] is the minimal (resp. maximal) length of right seeds of $y[0\mathinner{\ldotp\ldotp} i]$ . We present an $\ensuremath{\mathcal{O}}(n\log n)$ time algorithm that computes the minimal right-seed array of a given string, and a linear-time solution to compute the maximal right-seed array by detecting border-free prefixes of the given string.

Url:

https://api.istex.fr/document/943A61B48CE2151B556A488A6F66336B6CB793CF/fulltext/pdf

DOI: 10.1007/978-3-642-22685-4_43

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Istex, to step Corpus: 001C05
to stream Istex, to step Curation: 001C05
to stream Istex, to step Checkpoint: 000787
to stream Main, to step Merge: 006744
to stream Main, to step Curation: 006368

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the Right-Seed Array of a String</title>
<author><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name>
</author>
<author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
</author>
<author><name sortKey="Guth, Ondrej" sort="Guth, Ondrej" uniqKey="Guth O" first="Ondrej" last="Guth">Ondrej Guth</name>
</author>
<author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
</author>
<author><name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:943A61B48CE2151B556A488A6F66336B6CB793CF</idno>
<date when="2011" year="2011">2011</date>
<idno type="doi">10.1007/978-3-642-22685-4_43</idno>
<idno type="url">https://api.istex.fr/document/943A61B48CE2151B556A488A6F66336B6CB793CF/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001C05</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001C05</idno>
<idno type="wicri:Area/Istex/Curation">001C05</idno>
<idno type="wicri:Area/Istex/Checkpoint">000787</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000787</idno>
<idno type="wicri:doubleKey">0302-9743:2011:Christou M:on:the:right</idno>
<idno type="wicri:Area/Main/Merge">006744</idno>
<idno type="wicri:Area/Main/Curation">006368</idno>
<idno type="wicri:Area/Main/Exploration">006368</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On the Right-Seed Array of a String</title>
<author><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name>
<affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Informatics, King’s College London, WC2R 2LS, London</wicri:regionArea>
<placeName><settlement type="city">Londres</settlement>
<region type="country">Angleterre</region>
<region type="région" nuts="1">Grand Londres</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country>
</affiliation>
</author>
<author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
<affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Informatics, King’s College London, WC2R 2LS, London</wicri:regionArea>
<placeName><settlement type="city">Londres</settlement>
<region type="country">Angleterre</region>
<region type="région" nuts="1">Grand Londres</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>Université Paris-Est</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country>
</affiliation>
</author>
<author><name sortKey="Guth, Ondrej" sort="Guth, Ondrej" uniqKey="Guth O" first="Ondrej" last="Guth">Ondrej Guth</name>
<affiliation></affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">République tchèque</country>
</affiliation>
</author>
<author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
<affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Informatics, King’s College London, WC2R 2LS, London</wicri:regionArea>
<placeName><settlement type="city">Londres</settlement>
<region type="country">Angleterre</region>
<region type="région" nuts="1">Grand Londres</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country xml:lang="fr">Australie</country>
<wicri:regionArea>Digital Ecosystems & Business Intelligence Institute, Curtin University, GPO Box U1987, 6845, Perth, WA</wicri:regionArea>
<wicri:noRegion>WA</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country>
</affiliation>
</author>
<author><name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
<affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Informatics, King’s College London, WC2R 2LS, London</wicri:regionArea>
<placeName><settlement type="city">Londres</settlement>
<region type="country">Angleterre</region>
<region type="région" nuts="1">Grand Londres</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2011</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Array</term>
<term>Cambridge university press</term>
<term>Christou</term>
<term>Constant factor</term>
<term>Corresponding factor</term>
<term>Corresponding factor length</term>
<term>Corresponding factor length range mini maxi</term>
<term>Crochemore</term>
<term>Data structures</term>
<term>Empty string</term>
<term>Linear time</term>
<term>Maximal</term>
<term>Maximal array</term>
<term>Maximal right seed</term>
<term>Minimal array</term>
<term>Minimal right seed</term>
<term>Minimal right seeds</term>
<term>Partitioning</term>
<term>Partitioning algorithm</term>
<term>Queue</term>
<term>Resp</term>
<term>Right seed</term>
<term>Right seeds</term>
<term>Superstring</term>
<term>Time requirements</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term>
<term>Array</term>
<term>Cambridge university press</term>
<term>Christou</term>
<term>Constant factor</term>
<term>Corresponding factor</term>
<term>Corresponding factor length</term>
<term>Corresponding factor length range mini maxi</term>
<term>Crochemore</term>
<term>Data structures</term>
<term>Empty string</term>
<term>Linear time</term>
<term>Maximal</term>
<term>Maximal array</term>
<term>Maximal right seed</term>
<term>Minimal array</term>
<term>Minimal right seed</term>
<term>Minimal right seeds</term>
<term>Partitioning</term>
<term>Partitioning algorithm</term>
<term>Queue</term>
<term>Resp</term>
<term>Right seed</term>
<term>Right seeds</term>
<term>Superstring</term>
<term>Time requirements</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We consider the problem of finding the repetitive structure of a given fixed string y. A factor u of y is a cover of y, if every letter of y falls within some occurrence of u in y. A factor v of y is a seed of y, if it is a cover of a superstring of y. There exist linear-time algorithms for solving the minimal cover problem. The minimal seed problem is of much higher algorithmic difficulty, and no linear-time algorithm is known. In this article, we solve one of its variants – computing the minimal and maximal right-seed array of a given string. A right seed of y is the shortest suffix of y that it is a cover of a superstring of y. An integer array RS is the minimal right-seed (resp. maximal right-seed) array of y, if RS[i] is the minimal (resp. maximal) length of right seeds of $y[0\mathinner{\ldotp\ldotp} i]$ . We present an $\ensuremath{\mathcal{O}}(n\log n)$ time algorithm that computes the minimal right-seed array of a given string, and a linear-time solution to compute the maximal right-seed array by detecting border-free prefixes of the given string.</div>
</front>
</TEI>
<affiliations><list><country><li>Australie</li>
<li>France</li>
<li>Royaume-Uni</li>
<li>République tchèque</li>
</country>
<region><li>Angleterre</li>
<li>Grand Londres</li>
</region>
<settlement><li>Londres</li>
</settlement>
</list>
<tree><country name="Royaume-Uni"><region name="Angleterre"><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name>
</region>
<name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name>
<name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
<name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
<name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
<name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
<name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
<name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
</country>
<country name="France"><noRegion><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
</noRegion>
</country>
<country name="République tchèque"><noRegion><name sortKey="Guth, Ondrej" sort="Guth, Ondrej" uniqKey="Guth O" first="Ondrej" last="Guth">Ondrej Guth</name>
</noRegion>
</country>
<country name="Australie"><noRegion><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006368 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006368 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Asie
   |area=    AustralieFrV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:943A61B48CE2151B556A488A6F66336B6CB793CF
   |texte=   On the Right-Seed Array of a String
}}

This area was generated with Dilib version V0.6.33.
Data generation: Tue Dec 5 10:43:12 2017. Site generation: Tue Mar 5 14:07:20 2024

	Serveur d'exploration sur les relations entre la France et l'Australie
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur les relations entre la France et l'Australie

On the Right-Seed Array of a String

On the Right-Seed Array of a String

Source :

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri